The invention relates to apparatus and methods of multiplexing data to a communication channel.
In a typical data network, a plurality of data sources deliver their respective data streams to various receivers over the same fixed bandwidth communication channel. A multiplexer receives the data streams from the sources and choreographs the injection of data into the communication channel. The multiplexer is typically designed to efficiently inject as much data into communication channel as possible, without exceeding the capacity of the channel. The data sources typically include encoders for compressing data before delivery to the multiplexer; the receivers decompress and reconstruct the original data signals from the compressed data streams. A data source may be characterized as either a constant bit rate (CBR) source or a variable bit rate (VBR) source: a fixed rate source injects data (bits) into a communication channel at a constant rate, whereas a variable rate source injects bits into a communication channel at a variable rate.
Transfer of information from the data sources is typically in the form of information packets. The multiplexer schedules data for output to the communication channel one packet at a time, and delivers the scheduled data packets to the channel as an output multiplex. Packet scheduling involves the assignment of a particular source to a timeslot in the output multiplex. A high-performance scheduling algorithm allows each of the sources to be assigned an arbitrary fraction of channel bandwidth, subject to the constraint that the sum of all source bit rates is less than or equal to the bit rate multiplex that they share. Real-time scheduling is desirable because it allows sources to change their bit rates frequently and on-the-fly. High-performance real-time scheduling of multiple sources often requires substantial hardware resources, with the computational complexity increasing with the output bit rate, the number of sources and the resolution with which the route of each source is specified.
The invention features apparatus and methods for multiplexing data received from a plurality of sources to a communication channel. In accordance with the invention, each of the sources is assigned to one of at least two scheduling layers, including a first layer and a second layer, based at least in part upon one or more bit rate characteristics of the sources.
Embodiments may include one or more of the following features.
Each of the sources may be assigned based at least in part on data transmission rates of the sources, bit rate precision levels of the sources or both. The sources may be assigned to the scheduling layers based upon a fixed assignment method that operates independently of changes in data transmission rates of the sources, or based upon a dynamic assignment method that responds to changes in data transmission rates of the sources. The number of sources assigned to the first layer may be fixed or variable.
In one embodiment, the first layer comprises an entry for each source assigned to the first layer and an entry representative of a source assigned to the second layer, and the second layer comprises an entry for each source assigned to the second layer. The sources represented by entries in the first layer are scheduled for output to the communication channel. The sources represented by entries in the first layer may be scheduled for output based upon a variable bit rate scheduling method. Sources with relatively high bit rates (with relatively high bit rate precision levels) preferably are assigned to the first layer. The sources represented by entries in the second layer are scheduled for assignment to the representative entry of the first layer. The sources represented by entries in the second layer preferably are scheduled sources for assignment to the representative entry of the first layer based upon a variable bit rate scheduling method.
In another embodiment, each of the sources is assigned to one of three or more scheduling layers, including the first layer, the second layer and a sequence of one or more lower layers, based at least in part on one or more bit rate characteristics of the sources. The second layer preferably comprises, in addition to an entry for each source assigned to the second layer, an entry representative of a source assigned to a first of the one or more lower layers, and each lower layer preferably comprises an entry for each source assigned to that lower layer and an entry representative of a source assigned to the next lower layer in the sequence of one or more lower layers. The sources represented by entries in that first lower layer preferably are scheduled for assignment to the representative entry of the second layer. In some embodiments, the first layer preferably comprises, in addition to the entry for each source assigned to the first layer and the entry representative of a source assigned to the second layer, a representative entry for each of the lower layers, and each lower layer preferably comprises an entry for each source assigned to that lower layer. Lower layer sources preferably are scheduled for assignment to the representative entries of the first layer.
In another embodiment, each of the sources is assigned to one of three or more scheduling layers, including the first layer, the second layer and a third layer, based at least in part on one or more bit rate characteristics of the sources. The first layer comprises an entry for each source assigned to the first layer. The second layer comprises an entry for each source assigned to the second layer. The third layer comprises an entry representative of a source assigned to the first layer and an entry representative of a source assigned to the second layer. Each of the sources preferably is assigned based at least in part on the data transmission rates of the sources, or on the bit rate precision levels of the sources. Sources with relatively high bit rates (or with relatively high bit rate precision levels) preferably are assigned to the first layer.
Each source preferably is assigned a data transmission rate and a bit rate precision level. In some embodiments, the same bit rate precision level is assigned to each source. In other embodiments, different bit rate precision levels are assigned to the sources. In a preferred embodiment, relatively high bit rate precision levels are assigned to audio sources, intermediate bit rate precision levels are assigned to video sources, and relatively low bit rate precision levels are assigned to data sources.
Among the advantages of the invention are the following.
The invention allows real-time scheduling using high performance scheduling methods, but with reduced computational requirements. Because each of the sources assigned to the first layer has a relatively high bit rate (or high bit rate precision level), the first layer sources typically may be scheduled with a course bit rate granularity. This reduces the computational load at the first layer without degrading the performance of the first layer sources (i.e., source performance is typically not degraded if it operates at 15.000 Mb/s rather than at 14.999 Mb/s, but its performance may be degraded if it operates at 1 kb/s).
The computational load at the lower (e.g., second) layer is reduced in several ways. The lower layer scheduler only need operate at the rate at which the first layer scheduler selects packets from the lower layer for output to the communication channelxe2x80x94a rate which may be a small fraction of the first layer packet rate. Further, the lower layer may only contain sources with a much smaller maximum bit rate than the first layer. This allows the use of scheduling methods characterized by a relatively fine bit rate granularity without increasing computational complexity. Sources may be assigned to layers depending on their bit rates and on their bit rate resolution requirements.
In addition, because the outputs of higher bit rate sources tend to be more regular than the outputs of lower bit rate sources, the invention might improve the overall multiplexer output regularity by separately scheduling the higher and lower bit rate sources.
The invention also reduces implementation complexity by separately scheduling high rate sources and low rate sources, or by separately scheduling fine rate granularity and coarse rate granularity sources, or both.
Other features and advantages will become apparent from the following description, including the drawings and the claims.